package com.fang.algorithm.sort.insert;

import com.fang.algorithm.common.SwapUtils;

import java.util.Arrays;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 插入排序
 * @date 2022/1/5 3:46 下午
 **/
public class Test01_Insert {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 5, 6, 4};
//        swapInsertSort(arr);
//        moveInsertSort(arr);
        test01InsertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void test01InsertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            // 0-1 有序
            // 0-2 有序
            // 0-i 有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                // 往前比较只要小就交换
                int temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }

    private static void moveInsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];
            int j = i - 1;
            // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
            while (j >= 0 && arr[j] < current) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 两种情况会跳出循环：
            // 1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
            // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
            arr[j + 1] = current;
        }
    }

    private static void swapInsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j >= 1 && arr[j] < arr[j - 1]) {
                SwapUtils.arrSwap(arr, j, j - 1);
                j--;
            }
        }
    }
}
